The present invention relates generally to coordination amongst execution sequences in a multiprocessor, and more particularly, to techniques for coordinating access to shared data and pointer encodings.
For over a decade, 64-bit architectures have been available. These architectures support 64-bit addresses, allowing direct access to huge virtual address spaces. Such architectures typically support atomic access to 64-bit quantities using synchronization primitives such as compare-and-swap (CAS) operations and/or load-linked/store conditional (LL/SC) operation pairs, which provide powerful tools for implementing lock-free data structures.
Operating systems and application software that exploit these 64-bit capabilities have been slower to emerge. Thus, many important 32-bit operating systems and applications are still in common use, and most 64-bit architectures support them. As a result, for several years, techniques that use 64-bit synchronization primitives to atomically manipulate 32-bit pointers together with other information (up to 32 additional bits), such as version numbers, have been widely applicable and many practical lock-free data structures exploit such techniques. Indeed, correctness of many such implementations hinges on the ability to atomically manipulate quantities that are wider than the pointers employed.
The increasing prevalence of 64-bit operating systems and applications (in which pointers are 64 bits) signals the end of this convenient era. As a result, 64-bit-clean lock-free data structures (which do not require synchronization primitives that can atomically manipulate a pointer and a version number) are increasingly important.